package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年4月26日
*时间：下午4:59:05
*/
public class Q512 {
    /**
     * @param s a string,  encoded message
     * @return an integer, the number of ways decoding
     */
    public int numDecodings(String s) {
        if (s == null || s.length() <= 0) {
            return 0;
        }
        if (s.startsWith("0")) {
            return 0;
        }
        int a[] = new int[s.length()+1];
        a[0]=1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
            	if(s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {
            		a[i+1] += a[i-1];
            	}else {
            		return 0;
            	}
            }else if(s.charAt(i) >= '1' && s.charAt(i) <= '6') {
            	if(s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {
            		a[i+1] += (a[i-1] + a[i]);
            	}else {
            		a[i+1] += a[i];
            	}
            }else if(s.charAt(i) > '6') {
            	if(s.charAt(i - 1) == '1') {
            		a[i+1] += (a[i-1] + a[i]);
            	}else {
            		a[i+1] += a[i];
            	}
            }
        }
        return a[s.length()];
    }

    @Test
    public void testA() {
        System.out.println(numDecodings("11111878787676172120121101212918291829819"));
    }
}
